1. Field of the Invention
This invention relates to memory management systems suitable for use with graphic systems. More particularly, this invention relates to using forward progress information to manage physical page memory to ensure that graphic system memory clients make forward progress.
2. Description of the Related Art
Computer systems invariably include memory. In fact, most computer system have many different types and classes of memories, e.g., main memory, cache memory, read-only memory, random access memory, hard disk memory, flash memory, and so on. However, a simple reference to computer memory usually refers to the main memory that stores the program instructions that a processor executes as well as the data that those instructions use and produce.
The amount and type of main memory is very important to overall system performance. Main memory systems can be and usually are comprised of both dynamic random access memory (DRAM) and disk memory. DRAM is very fast; data reads and writes often occur in times measured in nanoseconds. Unfortunately, while fast, DRAM is also relatively expensive. That expense tends to limit the amount of DRAM that is available. To augment their DRAM, modern computers incorporate disk memory into their main memory systems. Disk memory is very slow when compared to DRAM, having read and write times measured in milliseconds. Beneficially however, disk memory is much cheaper than DRAM. While what follows often discusses disk memory, primarily because disk memory is so common, in practice when disk memory is used it should be understood that other types of memory, for example, “ram disk” memory also can be used. It should also be understood that in the context of discussing virtual memory systems, the term “physical memory” applies to the system's DRAM.
The need to integrate both physical memory and disk memory to form the illusion of an integrated main memory has lead to the development of virtual memory systems and virtual memory managers. A virtual memory manager can enable an application (computer program) running on a computer system to be able to uniformly access far more memory than the computer actually has in physical memory. The application is said to access “virtual memory” whose underlying storage is actually made up of a combination of physical and disk memory, which is managed behind the scenes (from the point of view of the software application) by the virtual memory manager.
Most virtual memory managers use the concept of pages. Programs and their associated data are stored in pages, with the frequently used pages being kept available in physical memory. Less often used pages are stored in disk memory. When a page that is not in physical memory is required by the software application, the operating system/virtual memory manager asserts a page fault exception. When a page fault exception occurs the virtual memory manager causes a requested page that is in disk memory to be inserted into physical memory and the displaced page in physical memory is moved to disk memory to make room for the incoming page. This process is called page swapping.
Virtual memory systems and virtual memory managers are implemented using a combination of hardware mechanisms and operating system software mechanisms. For performance efficiency, virtual memory systems are usually implemented in such a way that when a virtual memory access by an application would result in a physical memory access without requiring any page swap, the requisite physical access would normally be made entirely using hardware mechanisms that are much faster than software.
The page replacement algorithm, also referred to as the page manager, of the manager component of the virtual memory subsystem is responsible for deciding which page to evict from physical memory and write back to disk in order to make space for the requested page. The page manager is also responsible for initiating the associated transfers between DRAM and disk. The page manager updates various tables that the hardware and software use to keep track of the mapping between virtual pages and DRAM or disk pages. Because the page manager is usually implemented in software and because it can afford to take some time to make a decision, the page manager can use relatively sophisticated algorithms to decide which page's eviction is likely to be least detrimental to system performance.
Virtual memory systems are very useful since they allow a computer to run software applications (or programs) that require more memory than the available physical memory, while not burdening the software application (or its programmer) with any knowledge of the underlying composition of the storage that the program is running on (or will run on). Furthermore, virtual memory allows each computer program to run in a private virtual memory context, which gives a program the illusion that it can use the same virtual memory address range each time that it runs, even if other programs (or other instances of the same program) are running (or will run) on the system concurrently with that program. This per-program instance of a virtual memory context enables modern multitasking such as running a word processor, a graphics program, a spreadsheet, and a database all at the same time, and without requiring any one of those program to have knowledge that there may be other programs running concurrently.
While highly beneficial, virtual memory systems are not without problems. If a computer system has insufficient physical memory, the virtual memory manager can cause constant (or almost constant) page swapping, a condition called thrashing, which leads to poor system performance. However, this problem is generally well understood and is typically addressed by incorporating sufficient physical memory to prevent or to reduce thrashing to an acceptable level.
While prior art computer systems have benefited from virtual memory and virtual memory managers, the prior art approach to virtual memory management may be insufficient to handle the memory requirements of modern and future graphics processing units (GPUs). Over recent years graphics processing has developed into extremely high speed, parallel processing systems composed of multiple memory clients that can perform mathematical and related operations on very large amounts of data that must be read from and/or written to the GPU's main memory. It should be noted that traditionally (i.e., in GPUs that do not implement virtual memory), a GPU's main memory is often referred to as the “frame buffer.”
In graphics terminology, a “memory client” is a hardware entity within the GPU that can process data that is stored in the GPU's main memory to achieve a desired result. For example, a graphical processing device produced by the assignee of the present invention includes multiple shader pipelines, each having multiple processing stations (such as texture stations), and each of which can be individually programmed to process segments of data. Each pipeline's texture station would be a memory client because it reads and operates on texture data stored in the GPU's main memory to achieve a desired result for which the pipeline is programmed. Other clients can include raster operation processors, rasterizers, geometry engines, etc.
Graphic processing programs can be divided up into groups of specific tasks that are to be accomplished. Those tasks are referred to herein as contexts. A context itself can be divided into threads, with a thread being a portion of the context that can be “completed.” That is a thread produces a given result that can then be used by other threads. In doing so a thread “retires data” in that the data is no longer required by the thread.
A challenge presented by modern graphical systems is ensuring that each memory client has the information (program and data) required to perform its assigned tasks. As the number of clients increases and as the amount of data each client can process increases it becomes very important, and more difficult, to ensure that all clients are actually making progress. Page swapping, while beneficial, cannot by itself ensure that multiple clients make progress.
The underlying problem is that the multiple memory clients may be competing against each other for the same physical memory. The problem is further exacerbated by the fact that all the clients may need to work cooperatively, requiring certain pages from each clients to be concurrently present in physical memory in order to finish processing some work before encountering another page fault. For example, if one client needs four pages to make progress, but one page is missing, another client might need several additional pages. Then, one of the four required pages for the first client might be swapped out of physical memory into disk memory to make room for a page required by the second client. Because of other clients causing page swaps the first client may never have access to all of the pages it needs to make progress. Likewise, the other clients may never have access to all of the pages they need to make progress. The result is excessive thrashing and possibly a frozen graphics system.
Therefore, a method of ensuring that required pages are available such that the graphical system makes progress would be beneficial. Also beneficial would be a simple hardware mechanism that can be used to ensure that forward progress is or will be made.